1. Field of the Invention
This invention relates generally to concurrent access to shared objects, and more particularly to a system and method for implementing shared scalable nonzero indicators.
2. Description of the Related Art
Shared counters are useful for a variety of purposes and been heavily studied as an important basic building block in many concurrent algorithms. This research has shown that it is very challenging to achieve a non-blocking solution that combines the desirable properties of linearizability, scalability (i.e., being independent of the number of threads/processes), and low latency.
Reference counters are used in a variety of contexts for determining when a resource is no longer in use and can thus be reclaimed. For example, some garbage collectors use reference counting to determine when an object is no longer reachable. Unfortunately, however, occasionally an object is heavily shared, meaning that many processes or threads access the reference count at once, resulting in poor scalability. While reference counting is a simple and attractive technique, it has the disadvantage that the use of simple counters to track references inhibits scalability; this factor alone can make reference counting unacceptable in some contexts.
Traditional counters provide increment and decrement operations that return the value of the counter immediately before the modification, and sometimes a read operation that returns the counter's value without modifying it. It is straightforward to implement a non-blocking shared counter in modem shared memory multi-processors, for example by repeatedly using the compare-and-swap (CAS) instruction to attempt to update the counter. While this approach is simple, non-blocking, linearizable, and reasonably fast in the absence of contention, it is not scalable. Severe performance degradation occurs under heavy use, as contention for the counter arises, as well as excessive memory interconnect traffic produced by successful and failed attempts. For example, if two threads increment a shared counter at approximately the same time, they must receive different and consecutive return values, and thus they must synchronize. An implementation that must be fast in the absence of contention must detect such contention quickly when it occurs. This is difficult, if not impossible, using traditional counter semantics.